#!/usr/bin/python

import collections
import random

class PercolationThreshold(object):

  def __init__(self, x):
    self.size = x * x + 2  # we have two virtual systems for connectiviy checks.
    self.x = x
    self.id_list = range(self.size)
    self.num_open = 0
    self.upper_virtual = self.size - 2
    self.lower_virtual = self.size - 1
    self.id_status = collections.defaultdict(int)
    for system in (self.upper_virtual, self.lower_virtual):
      self.id_status[system] = 1

  @property
  def threshold(self):
    return float(self.num_open) / (self.size - 2)

  def GetNeighbors(self, object_id):
    result = []
    if object_id < 0 or object_id > self.size - 3:
      return result
    # Upper neighbor:
    upper_neighbor = object_id - self.x
    if upper_neighbor >= 0:
      result.append(upper_neighbor)

    # Lower neighbor:
    lower_neighbor = object_id + self.x
    if lower_neighbor <= self.size - 3:
      result.append(lower_neighbor)

    # Right neighbor:
    right_neighbor = object_id + 1
    if object_id % self.x < self.x - 1 and right_neighbor <= self.size - 2:
      result.append(right_neighbor)

    # Left neighbor:
    left_neighbor = object_id - 1
    if object_id % self.x > 0 and left_neighbor >= 0:
      result.append(left_neighbor)

    # Upper virtual.
    if object_id < self.x:
      result.append(self.upper_virtual)

    # Lower virtual.
    if object_id >= self.size - self.x - 2:
      result.append(self.lower_virtual)

    return sorted(result)

  def IsOpen(self, object_id):
    return bool(self.id_status[object_id])

  def GetRoot(self, object_id):
    while not self.id_list[object_id] == object_id:
      # Point each object on the path to root to its grandparent.
      current_parent = self.id_list[object_id]
      grandparent = self.id_list[current_parent]
      self.id_list[object_id] = grandparent
      object_id = self.id_list[object_id]
    return object_id

  def connected(self, p, q):
    return self.GetRoot(p) == self.GetRoot(q)

  def union(self, p, q):
    p_root = self.GetRoot(p)
    q_root = self.GetRoot(q)
    self.id_list[p_root] = q_root

  def Run(self):
    for system in self.id_list:
      status = random.choice((True, False))
      if status:
        self.num_open += 1
        self.id_status[system] = 1
        for neighbor in self.GetNeighbors(system):
          if self.id_status[neighbor]:
            self.union(system, neighbor)
        if self.connected(self.upper_virtual, self.lower_virtual):
          break

def main():
  # Monte carlo.
  results = []
  for test_num in range(100000):
    pt = PercolationThreshold(10)
    pt.Run()
    results.append(pt.threshold)
  print 'Result: %.10f' % (sum(results) / len(results))
  

if __name__ == '__main__':
  main() 
